# 给你一个整数数组 nums 和一个整数 target 。
#
# 向数组中的每个整数前添加'+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
#
# 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
# 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
#
#
# 示例 1：
#
# 输入：nums = [1,1,1,1,1], target = 3
# 输出：5
# 解释：一共有 5 种方法让最终目标和为 3 。
# -1 + 1 + 1 + 1 + 1 = 3
# +1 - 1 + 1 + 1 + 1 = 3
# +1 + 1 - 1 + 1 + 1 = 3
# +1 + 1 + 1 - 1 + 1 = 3
# +1 + 1 + 1 + 1 - 1 = 3
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/target-sum
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
from typing import List


class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        n = len(nums)
        f = [0] * 2001
        f[nums[0] + 1000] += 1
        f[-nums[0] + 1000] += 1
        for i in range(1, n):
            g = [0] * 2001
            for j in range(-1000, 1001, 1):
                if f[j + 1000] > 0:
                    g[j + 1000 + nums[i]] += f[j + 1000]
                    g[j + 1000 - nums[i]] += f[j + 1000]
            f = g
        return f[S + 1000]


if __name__ == '__main__':
    sol = Solution()
    print(sol.findTargetSumWays(nums=[1, 1, 1, 1, 1], S=3))
